class Solution {//leetcode21——合并两个有序链表
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* first=list1;//双指针，一个指针遍历链表1，一个负责遍历链表2
        ListNode* second=list2;
        ListNode* temp=new ListNode(0,nullptr);//创建一个临时的链表
        ListNode* tempcur=temp;
        while(first!=nullptr&&second!=nullptr){
            ListNode* cur=nullptr;
            if(first->val>second->val){
                cur=second;
                second=second->next;
                tempcur->next=cur;
            }
            else //链表1的当前节点小于等于链表2的当前节点{
                cur=first;
                first=first->next;
                tempcur->next=cur;
            }
            tempcur->next=cur;
            tempcur=tempcur->next;
        }
        if(first==nullptr)
            tempcur->next=second;
        else
            tempcur->next=first;
        ListNode* ret=temp->next;
        delete temp;
        return ret;
    }
};